package 统计好节点的数目3249;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    HashSet<Integer> set = new HashSet<>();
    int count = 0;
    public int countGoodNodes(int[][] edges) {
        for (int[] edge : edges) {
            if (!map.containsKey(edge[0])) {
                map.put(edge[0], new ArrayList<>());
            }
            if (!map.containsKey(edge[1])) {
                map.put(edge[1], new ArrayList<>());
            }
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        dfs(0);
        return count;
    }
    int dfs(int i) {
        set.add(i);
        if(!map.containsKey(i)) {
            count++;
            return 1;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (Integer key : map.get(i)) {
            if (set.contains(key)) {
                continue;
            }
            list.add(dfs(key));
        }
        if(list.isEmpty()) {
            count++;
            return 1;
        }
        int sum = list.get(0);
        int temp = list.get(0);
        boolean sign = true;
        for (int j = 1; j < list.size(); ++j) {
            sum += list.get(j);
            if(temp != list.get(j)) {
                sign = false;
            }
        }
        if(sign) {
            count ++;
        }
        return sum + 1;
    }
}
